/*
* $Id: tree_sort.hh 80333 2008-07-24 15:05:39Z lexus $
*
* Copyright 2008 by Sunbay Software Crimea Ltd.
* Prospekt Kirova 29/1 office 432, 95000 Simferopol, Ukraine
* All rights reserved
*
*/
#ifndef _tree_sort_hh_
#define _tree_sort_hh_

#include "tree.hh"

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> > >
class tree_sort : public tree<T, tree_node_allocator>, public IBase
{
public:
	tree_sort();
	tree_sort(const T&);
	tree_sort(const iterator_base& other);
	tree_sort(const tree_sort<T, tree_node_allocator>&);
	virtual ~tree_sort();

	template<typename iter> iter append_child(iter position, const T& x);
	template<typename iter> iter append_child(iter position, iter other_position);
	template<typename iter> iter insert(iter position, const T& x);
	template<typename iter> iter insert_subtree(iter position, iter other_position);
	sibling_iterator begin() const;
	sibling_iterator end() const;
	sibling_iterator begin(const iterator_base& iter) const;
	sibling_iterator end(const iterator_base& iter) const;
	sibling_iterator begin_sibling(const iterator_base& iter) const;
	sibling_iterator end_sibling(const iterator_base& iter) const;
	void Free();
};

template <class T, class tree_node_allocator>
tree_sort<T, tree_node_allocator>::tree_sort()
: tree(){}

template <class T, class tree_node_allocator>
tree_sort<T, tree_node_allocator>::tree_sort(const T& x)
: tree(x){}

template <class T, class tree_node_allocator>
tree_sort<T, tree_node_allocator>::tree_sort(const iterator_base& other)
: tree(other){}

template <class T, class tree_node_allocator>
tree_sort<T, tree_node_allocator>::tree_sort(const tree_sort<T, tree_node_allocator>& other)
: tree(other){}

template<class T, class tree_node_allocator>
tree_sort<T, tree_node_allocator>::~tree_sort(){}

template <class T, class tree_node_allocator>
template<class iter>
iter tree_sort<T, tree_node_allocator>::append_child(iter position, const T& x)
{
	iter it;
	if(begin(position) == end(position))
		it = __super::append_child(position, x);
	else
	{
		it = std::lower_bound(begin(position), end(position), x);
		if(it == end(position))
			it = __super::append_child(position, x);
		else
			it = __super::insert(it, x);
	}
	position.node->first_child = it.node->parent->first_child;
	position.node->last_child = it.node->parent->last_child;
	return it;
}

template <class T, class tree_node_allocator>
template<class iter>
iter tree_sort<T, tree_node_allocator>::append_child(iter position, iter other_position)
{
	iter it;
	if(begin(position) == end(position))
		it = __super::append_child(position, other_position);
	else
	{
		it = std::lower_bound(begin(position), end(position), *other_position);
		if(it == end(position))
			it = __super::append_child(position, other_position);
		else
			it = __super::insert(it, other_position);
	}
	position.node->first_child = it.node->parent->first_child;
	position.node->last_child = it.node->parent->last_child;
	return it;
}

template<class T, class tree_node_allocator>
template<class iter>
iter tree_sort<T, tree_node_allocator>::insert(iter position, const T& x)
{
	iter it;
	if(begin_sibling(position)== end_sibling(position))
		it = position;
	else
		it = std::lower_bound(begin_sibling(position), end_sibling(position), x);
	return __super::insert(it, x);
}

template<class T, class tree_node_allocator>
template<typename iter>
iter tree_sort<T, tree_node_allocator>::insert_subtree(iter position, iter other_position)
{
	iter it;
	if(position.parent_)
		it = end();
	if(position == end_sibling(position))
		it = position;
	else
		it = std::lower_bound(begin_sibling(position), end_sibling(position), *other_position);
	return __super::insert_subtree(it, other_position);
}

template<class T, class tree_node_allocator>
typename tree_sort<T, tree_node_allocator>::sibling_iterator 
tree_sort<T, tree_node_allocator>::begin_sibling(const iterator_base& iter) const
{
	if(!iter.node)
		return iter;
	else if(iter.node->parent)
		return begin(iter.node->parent);
	else
		return begin();
}

template<class T, class tree_node_allocator>
typename tree_sort<T, tree_node_allocator>::sibling_iterator 
tree_sort<T, tree_node_allocator>::end_sibling(const iterator_base& iter) const
{
	if(!iter.node)
		return iter;
	else if(iter.node->parent)
		return end(iter.node->parent);
	else
		return end();
}

template<class T, class tree_node_allocator>
typename tree_sort<T, tree_node_allocator>::sibling_iterator 
tree_sort<T, tree_node_allocator>::begin() const
{
	return __super::begin();
}

template<class T, class tree_node_allocator>
typename tree_sort<T, tree_node_allocator>::sibling_iterator 
tree_sort<T, tree_node_allocator>::end() const
{
	return __super::end();
}

template<class T, class tree_node_allocator>
typename tree_sort<T, tree_node_allocator>::sibling_iterator 
tree_sort<T, tree_node_allocator>::begin(const iterator_base& iter) const
{
	return __super::begin(iter);
}

template<class T, class tree_node_allocator>
typename tree_sort<T, tree_node_allocator>::sibling_iterator 
tree_sort<T, tree_node_allocator>::end(const iterator_base& iter) const
{
	return __super::end(iter);
}

template <class T, class tree_node_allocator>
void tree_sort<T, tree_node_allocator>::Free()
{
	delete this;
}

#endif